package org.xqh.study.leetcode.algorithm;

/**
 * @ClassName RegionsCutBySlashes
 * @Description https://leetcode-cn.com/problems/regions-cut-by-slashes/
 * 由斜杠划分区域
 * @Author xuqianghui
 * @Date 2021/1/25 9:39
 * @Version 1.0
 */
public class RegionsCutBySlashes {

    public static void main(String[] args) {
//        String test = "/\\ ";
//        char[] array = test.toCharArray();
//        for(char c:array){
//            System.out.println((int)c);
//        }
        String[] grid = {"\\/", "/\\"};
        System.out.println(regionsBySlashes(grid));;
    }


    /**
     * 1 <= grid.length == grid[0].length <= 30
     * grid[i][j] 是 '/' = 47、'\' = 92、或 ' ' = 32。
     * <p>
     * 每个 方格 分为四块 .  0 / 1/ 2/ 3
     *
     * @param grid
     * @return
     */
    public static int regionsBySlashes(String[] grid) {
        int len = grid.length;
        int size = 4 * len * len;
        RegionUnion union = new RegionUnion(size);
        for (int i = 0; i < len; i++) {
            char[] array = grid[i].toCharArray();
            for (int j = 0; j < len; j++) {
                int index = (i * len + j) * 4;
                if (array[j] == ' ') {
                    //该方格内 是空格  合并 方格内的 四个 三角
                    union.union(index, index + 1);
                    union.union(index + 1, index + 2);
                    union.union(index + 2, index + 3);
                } else if (array[j] == '/') {
                    //合并当前方格 up + left, right + down
                    union.union(index, index + 3);
                    union.union(index + 1, index + 2);
                } else if( array[j] == '\\'){
                    //合并当前方格 的 up + right, down + left;
                    union.union(index, index + 1);
                    union.union(index + 2, index + 3);
                }
                // 当前方格 右边块 合并下一个方格 左边的块
                if (j != len - 1) {
                    //不是当前行最后一格
                    int rowNextIdx = (i * len + j + 1) * 4;
                    union.union(index + 1, rowNextIdx + 3);
                }
                //合并当前方格 的 down 和 下面方格的 up
                if (i != len - 1) {
                    //不是最后一列
                    int columnNextIdx = ((i + 1) * len + j) * 4;
                    union.union(index + 2, columnNextIdx);
                }
            }
        }
        return union.getCount();
    }

    public static class RegionUnion {
        private int[] parent;
        private int count;//当前块的个数

        public int getCount() {
            return count;
        }

        public RegionUnion(int size) {
            parent = new int[size];
            for (int i = 0; i < parent.length; i++) {
                parent[i] = i;
            }
            count = size;
        }

        /**
         * @param idx
         * @return
         */
        public int find(int idx) {
            while (parent[idx] != idx) {
                parent[idx] = parent[parent[idx]];
                idx = parent[idx];
            }
            return idx;
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;
            count--;
        }
    }
}
